{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Score of Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: scoreOfParentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #括号的分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个平衡括号字符串&nbsp;<code>S</code>，按下述规则计算该字符串的分数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>()</code> 得 1 分。</li>\n",
    "\t<li><code>AB</code> 得&nbsp;<code>A + B</code>&nbsp;分，其中 A 和 B 是平衡括号字符串。</li>\n",
    "\t<li><code>(A)</code> 得&nbsp;<code>2 * A</code>&nbsp;分，其中 A 是平衡括号字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入： </strong>&quot;()&quot;\n",
    "<strong>输出： </strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入： </strong>&quot;(())&quot;\n",
    "<strong>输出： </strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre><strong>输入： </strong>&quot;()()&quot;\n",
    "<strong>输出： </strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;4：</strong></p>\n",
    "\n",
    "<pre><strong>输入： </strong>&quot;(()(()))&quot;\n",
    "<strong>输出： </strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>S</code>&nbsp;是平衡括号字符串，且只含有&nbsp;<code>(</code>&nbsp;和&nbsp;<code>)</code>&nbsp;。</li>\n",
    "\t<li><code>2 &lt;= S.length &lt;= 50</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [score-of-parentheses](https://leetcode.cn/problems/score-of-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [score-of-parentheses](https://leetcode.cn/problems/score-of-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"()\"', '\"(())\"', '\"()()\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = bal = 0\n",
    "        for i, c in enumerate(s):\n",
    "            bal += 1 if c == '(' else -1\n",
    "            if c == ')' and s[i - 1] == '(':\n",
    "                ans += 1 << bal\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        bal = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='(':\n",
    "                bal += 1\n",
    "            else:\n",
    "                bal -= 1\n",
    "            if s[i] == ')' and s[i-1]=='(':\n",
    "                ans = ans + (1<<bal)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ret, stack = 0, []\n",
    "        for l in s:\n",
    "            if l == '(': stack.append(0)\n",
    "            else:\n",
    "                if stack[-1] == 0: stack[-1] += 1\n",
    "                else: stack[-1] *= 2\n",
    "                if len(stack) == 1: ret += stack.pop()\n",
    "                else:\n",
    "                    val = stack.pop()\n",
    "                    stack[-1] += val\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = [0]\n",
    "        cur = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(0)\n",
    "                # cur = 0\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if cur == 0:\n",
    "                    cur = 1 + stack.pop()\n",
    "                else:\n",
    "                    cur *= 2\n",
    "                    cur += stack.pop()\n",
    "                    \n",
    "                    \n",
    "                stack.append(cur)\n",
    "                \n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        st = [0]\n",
    "        pre = ''\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                cur = st.pop()\n",
    "                if pre == '(':\n",
    "                    cur += 1\n",
    "                else:\n",
    "                    cur *= 2\n",
    "                st[-1] += cur\n",
    "            pre = i\n",
    "        return st[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = bal = 0\n",
    "        for i, c in enumerate(s):\n",
    "            bal += 1 if c == '(' else -1\n",
    "            if c == ')' and s[i - 1] == '(':\n",
    "                ans += 1 << bal\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        #copy\n",
    "        stack = [0]\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(0)\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                stack.append(stack.pop()+max(cur*2,1)) \n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        index = 0 \n",
    "        a = \"\"\n",
    "        for c in s:\n",
    "            if index == 0:\n",
    "                last = c \n",
    "                index += 1\n",
    "            else:\n",
    "                if c == \"(\" and last == \"(\":\n",
    "                    a = a + \"2*(\"\n",
    "                elif c == \"(\" and last == \")\":\n",
    "                    a = a + \"+\"\n",
    "                elif c == \")\" and last == \"(\":\n",
    "                    a = a + \"1\"\n",
    "                else:\n",
    "                    a = a + \")\"\n",
    "                last = c\n",
    "        return eval(a)\n",
    "                  \n",
    "\n",
    "            \n",
    "\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = d = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "            else:\n",
    "                d -= 1\n",
    "                if s[i - 1] == '(':\n",
    "                    ans += 2**d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i]=='(':\n",
    "                stack.append(s[i])\n",
    "                continue\n",
    "            \n",
    "            elm = stack.pop()\n",
    "            if elm=='(':\n",
    "                num = 1\n",
    "                stack.append(num)\n",
    "            else:\n",
    "                num = 0\n",
    "                while elm!='(':\n",
    "                    num = num+elm\n",
    "                    elm = stack.pop()\n",
    "                stack.append(2*num)\n",
    "        res = 0\n",
    "        for i in stack:\n",
    "            res = res+i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        st = [0]\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                v = st.pop()\n",
    "                st[-1] += max(2 * v, 1)\n",
    "        return st[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                if stack[-1] == '(':\n",
    "                    stack.pop()\n",
    "                    stack.append(1)\n",
    "                else:\n",
    "                    temp = 0\n",
    "                    while stack[-1] != '(':\n",
    "                        temp += stack.pop()\n",
    "                    stack.pop()\n",
    "                    stack.append(temp*2)\n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        st = [0]\n",
    "        depth = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                score = st[-1]\n",
    "                if score == 0:\n",
    "                    score = 1\n",
    "                else:\n",
    "                    score *= 2\n",
    "                st.pop()\n",
    "                st[-1] += score\n",
    "        return st[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        st = [0]\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                v = st.pop()\n",
    "                st[-1] += max(1, v * 2)\n",
    "        return st[-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "      stack = []\n",
    "      score = []\n",
    "      for c in s:\n",
    "        if c == '(':\n",
    "          stack.append(c)\n",
    "        else:\n",
    "          stack.pop()\n",
    "          layer = len(stack)\n",
    "          if not score:\n",
    "            score.append([layer, 1])\n",
    "            continue\n",
    "          if score[-1][0] < layer:\n",
    "            score.append([layer, 1])\n",
    "          elif score[-1][0] == layer:\n",
    "            score[-1][1] += 1\n",
    "          else:\n",
    "            _, s = score.pop()\n",
    "            val = 2*s\n",
    "            if score and layer == score[-1][0]:\n",
    "              score[-1][1] += val\n",
    "            else:\n",
    "              score.append([layer, val])\n",
    "      return score[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                last = stack.pop()\n",
    "                if last=='(':\n",
    "                    stack.append(1)\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    stack.append(2*last)\n",
    "            print(c,stack)\n",
    "            res = 0\n",
    "            while stack and stack[-1]!='(':\n",
    "                res += stack.pop()\n",
    "            if res:\n",
    "                stack.append(res)\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        d=[0]\n",
    "        for x in s:\n",
    "            if x=='(':\n",
    "                d.append(0)\n",
    "            else:\n",
    "                cur=d.pop()\n",
    "                d.append(d.pop()+max(cur*2,1))\n",
    "        return d[-1]\n",
    "        #0 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        cnt = ans = 0\n",
    "        last = False    # 上一个是否为正括号，只有正反括号才会加\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cnt += 1\n",
    "                last = True\n",
    "            else:\n",
    "                if last:\n",
    "                    ans += 1 << cnt - 1\n",
    "                    last = False\n",
    "                cnt -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = d = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "            else:\n",
    "                d -= 1\n",
    "                if s[i - 1] == '(':\n",
    "                    ans += 1 << d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        r = []\n",
    "        t = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                stack.append(t)\n",
    "                stack.append(s[i])\n",
    "            #r.append(t)\n",
    "\n",
    "            else:\n",
    "                p = 0\n",
    "                while stack[-1]!='(':\n",
    "                    p += int(stack[-1])\n",
    "                    stack.pop()\n",
    "                if p==0:\n",
    "                    stack.pop()\n",
    "                    stack.append('1')\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    stack.append(str(2*p))\n",
    "        print(stack)\n",
    "        stack = [int(s) for s in stack]\n",
    "        return sum(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "\n",
    "            if not s:\n",
    "                return 0\n",
    "            if s=='()':\n",
    "                return 1\n",
    "            if s[0]=='(':\n",
    "                pairs=1\n",
    "                r=1\n",
    "                while pairs!=0:\n",
    "                    if s[r]=='(':\n",
    "                        pairs+=1\n",
    "                    else:\n",
    "                        pairs-=1\n",
    "                    r+=1\n",
    "                if r==2:\n",
    "                    return 1+self.scoreOfParentheses(s[2:])\n",
    "                return 2*self.scoreOfParentheses(s[1:r-1])+self.scoreOfParentheses(s[r:])\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "\n",
    "        for ii in s:\n",
    "            if ii == '(':\n",
    "                stack.append(ii)\n",
    "            else:\n",
    "                current_sum = 0\n",
    "                while stack and type(stack[-1]) is int:\n",
    "                    current_sum += stack.pop()\n",
    "                \n",
    "                stack.pop()\n",
    "                stack.append(max(current_sum * 2, 1))\n",
    "        \n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "\n",
    "        st = [0]\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                v = st.pop()\n",
    "                if v==0:\n",
    "                    st[-1] += 1\n",
    "                else:\n",
    "                    st[-1] += 2*v\n",
    "        return st[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        st = [0]\n",
    "        for ch in s:\n",
    "            if ch =='(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                v = st.pop()\n",
    "                st[-1] += max(2*v,1)\n",
    "        return st[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        st = [0]\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                v = st.pop()\n",
    "                st[-1] += max(2 * v, 1)\n",
    "        return st[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scoreOfParentheses(self, s: str) -> int:\r\n",
    "        st=[0]\r\n",
    "        for c in s:\r\n",
    "            if c=='(':\r\n",
    "                st.append(0)\r\n",
    "            else:\r\n",
    "                v=st.pop()\r\n",
    "                st[-1]+=max(v*2,1)\r\n",
    "        return st[-1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        l = [0]\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                l.append(0)\n",
    "            else:\n",
    "                v = l.pop()\n",
    "                l[-1] += max(2*v, 1)\n",
    "        return l[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scoreOfParentheses(self, s: str) -> int:\r\n",
    "        s=s.replace('()','1')\r\n",
    "        cnt=0\r\n",
    "        res=0\r\n",
    "        for i in s:\r\n",
    "            if i=='(':\r\n",
    "                cnt+=1\r\n",
    "            elif i=='1':    \r\n",
    "                res+=1<<cnt\r\n",
    "            else:\r\n",
    "                cnt-=1\r\n",
    "                    \r\n",
    "\r\n",
    "        return res           \r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                score = 0\n",
    "                while stack and stack[-1] != \"(\":\n",
    "                    score += stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append(max(score * 2, 1))\n",
    "            # print(stack)\n",
    "        return sum(stack)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        st = [0]\n",
    "        for i in s:\n",
    "            if i=='(':\n",
    "                st.append(0)\n",
    "            else:\n",
    "                v = st.pop()\n",
    "                st[-1]  = st[-1]+max(2*v,1)\n",
    "        return st[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scoreOfParentheses(self, s: str) -> int:\r\n",
    "        stack=[]\r\n",
    "        res=0\r\n",
    "        for i in s:\r\n",
    "            if i=='(':\r\n",
    "                stack.append(i)\r\n",
    "            else: \r\n",
    "                tmp=0               \r\n",
    "                while stack[-1]!='(':\r\n",
    "                    tmp+=stack.pop()\r\n",
    "                stack.pop()\r\n",
    "                stack.append(max(tmp*2,1))\r\n",
    "        return sum(stack)           \r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stk = [0]\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stk.append(0)\n",
    "            else:\n",
    "                v = stk.pop()\n",
    "                stk[-1] += max(2*v,1)\n",
    "        return stk[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        q = deque(list(s))\n",
    "        \n",
    "        while q:\n",
    "            top = q.popleft()\n",
    "            if top == '(':\n",
    "                stack.append(top)\n",
    "            else:\n",
    "                current = 0\n",
    "                while True:\n",
    "                    top = stack.pop()\n",
    "                    if top == '(':\n",
    "                        break\n",
    "                    current += top\n",
    "                current = max(current, 0.5)\n",
    "                stack.append(current * 2)\n",
    "        \n",
    "        return int(sum(stack))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack=[0] #开始前压入分数0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(0)\n",
    "            else:\n",
    "                v=stack.pop()\n",
    "                stack[-1] += max(2*v,1)\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        level = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                level += 1\n",
    "            else:\n",
    "                if stack and stack[-1][1] > level:\n",
    "                    cur = 0\n",
    "                    while stack and stack[-1][1] > level:\n",
    "                        cur += stack.pop()[0]\n",
    "                    cur *= 2\n",
    "                else:\n",
    "                    cur = 1\n",
    "                stack.append((cur, level))\n",
    "                level -= 1\n",
    "\n",
    "        return sum(x[0] for x in stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        #Divide & Conquor\n",
    "        start = 0 \n",
    "        end = len(s)-1\n",
    "        score = self.dfsHepler(s,start,end)\n",
    "        return score\n",
    "\n",
    "    def dfsHepler(self,s,start,end):\n",
    "          \n",
    "        score= 0 \n",
    "        nleft = 0 \n",
    "        nright = 0 \n",
    "        nextStart = start\n",
    "\n",
    "        for i in range(start,end+1):\n",
    "            if s[i] == '(':\n",
    "                nleft += 1 \n",
    "            elif s[i] == ')':\n",
    "                nright += 1\n",
    "            if nleft == nright:\n",
    "                if nleft == 1 and nright == 1:\n",
    "                    score += 1 \n",
    "                    nleft = 0\n",
    "                    nright = 0\n",
    "                    nextStart = i + 1\n",
    "                else:\n",
    "                    score += self.dfsHepler(s,nextStart+1,i-1)*2\n",
    "                    nleft = 0\n",
    "                    nright = 0\n",
    "                    nextStart = i + 1 \n",
    "        \n",
    "        return score\n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch == \"(\":\n",
    "                stack.append(\"(\")\n",
    "            else:\n",
    "                if stack[-1] == \"(\":\n",
    "                    stack[-1] = 1\n",
    "                else:\n",
    "                    cnt = 0\n",
    "                    while stack[-1] != \"(\":\n",
    "                        cnt += stack.pop()\n",
    "                    stack[-1] = cnt * 2\n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        i = 0\n",
    "        def dfs():\n",
    "            nonlocal i\n",
    "            res = 0\n",
    "            while i < len(s) and s[i] == \"(\":\n",
    "                i += 1\n",
    "                if s[i] == \")\":\n",
    "                    res += 1\n",
    "                else:\n",
    "                    res += dfs() * 2\n",
    "                i += 1\n",
    "            return res\n",
    "        return dfs()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = d = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "            else:\n",
    "                d -= 1\n",
    "                if s[i - 1] == '(':\n",
    "                    ans += 1 << d\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        cnt = ans = 0\n",
    "        last = False    # 上一个是否为正括号，只有正反括号才会加\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cnt += 1\n",
    "                last = True\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                if last:\n",
    "                    ans += 1 << cnt\n",
    "                    last = False\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scoreOfParentheses(self, s: str) -> int:\r\n",
    "        stack=[]\r\n",
    "        res=0\r\n",
    "        for i in s:\r\n",
    "            if i=='(':\r\n",
    "                stack.append(i)\r\n",
    "            else: \r\n",
    "                tmp=0               \r\n",
    "                while stack[-1]!='(':\r\n",
    "                    tmp+=stack.pop()\r\n",
    "                stack.pop()\r\n",
    "                stack.append(max(tmp*2,1))\r\n",
    "            print(stack)\r\n",
    "        return sum(stack)           \r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        def cal_parentheses(start_idx):\n",
    "            if s[start_idx] == ')':\n",
    "                return 1, start_idx\n",
    "            \n",
    "            ans = 0\n",
    "            ii = start_idx\n",
    "            while ii < len(s):\n",
    "                if s[ii] == '(':\n",
    "                    inside_ans, new_ii = cal_parentheses(ii + 1)\n",
    "                    ans += inside_ans\n",
    "                    ii = new_ii\n",
    "                elif s[ii] == ')':\n",
    "                    return ans * 2, ii\n",
    "\n",
    "                ii += 1\n",
    "            \n",
    "            return ans * 2, len(s) - 1\n",
    "        \n",
    "        return cal_parentheses(0)[0] // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = bal = 0\n",
    "        for i, c in enumerate(s):\n",
    "            bal += 1 if c == '(' else -1\n",
    "            if c == ')' and s[i-1] == '(':\n",
    "                ans += 1 << bal\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                ans = 0\n",
    "                while stack[-1] != '(':\n",
    "                    ans += stack.pop()\n",
    "                stack.pop()\n",
    "                if ans == 0:\n",
    "                    stack.append(1)\n",
    "                else:\n",
    "                    stack.append(2 * ans)\n",
    "        \n",
    "        return sum(stack)\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        depth, res = 0, 0\n",
    "        for i, c in enumerate(s):\n",
    "            depth += 1  if c == '(' else -1\n",
    "            if c == ')' and s[i-1] == '(':\n",
    "                res += 1 << depth\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        # 栈\n",
    "        stack = [0]\n",
    "\n",
    "        for i, x in enumerate(s):\n",
    "            \n",
    "            if x == '(':\n",
    "                stack.append(0)\n",
    "            else:\n",
    "                x = stack.pop()\n",
    "                stack[-1] += max(x * 2, 1)\n",
    "        \n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = d = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "            else:\n",
    "                d -= 1\n",
    "                if s[i - 1] == '(':\n",
    "                    ans += 2**d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        if s == '()':\n",
    "            return 1\n",
    "        else:\n",
    "            count = 1\n",
    "            ans = 0\n",
    "            pre = 0\n",
    "            for i in range(1, len(s)):\n",
    "                if s[i] == '(':\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count -= 1\n",
    "                if count == 0:\n",
    "                    if pre == 0 and i == len(s)-1:\n",
    "                        return 2 * self.scoreOfParentheses(s[1:len(s) - 1])\n",
    "                    else:\n",
    "                        ans += self.scoreOfParentheses(s[pre:i+1])\n",
    "                        pre = i+1\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = d = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "            else:\n",
    "                d -= 1\n",
    "                if s[i - 1] == '(':\n",
    "                    ans += 1 << d\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        def dfs(i, j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            res = 0\n",
    "            left = 1\n",
    "            start = i\n",
    "            for x in range(i+1, j):\n",
    "                if s[x] == '(':\n",
    "                    left += 1\n",
    "                else: \n",
    "                    left -= 1\n",
    "                if left == 0:\n",
    "                    ## \"()\"\n",
    "                    if x == start+1:\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        res += dfs(start+1, x) * 2\n",
    "                    start = x + 1\n",
    "            return res\n",
    "        return dfs(0, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        cnt = ans = 0\n",
    "        last = False    # 上一个是否为正括号，只有正反括号才会加\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cnt += 1\n",
    "                last = True\n",
    "            else:\n",
    "                if last:\n",
    "                    ans += 1 << cnt - 1\n",
    "                    last = False\n",
    "                cnt -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        bal = 0\n",
    "        for i, c in enumerate(s):\n",
    "            bal += 1 if c == '(' else -1\n",
    "            if bal == 0:\n",
    "                if i == n - 1:\n",
    "                    return 2 * self.scoreOfParentheses(s[1:-1])\n",
    "                return self.scoreOfParentheses(s[:i+1]) + self.scoreOfParentheses(s[i+1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        arr = [0]\n",
    "        pre = \"(\"\n",
    "        for c in s:\n",
    "            if c=='(':\n",
    "                arr.append(0)\n",
    "            else:\n",
    "                cur = arr.pop()\n",
    "                if pre == \"(\":\n",
    "                    cur += 1\n",
    "                else:\n",
    "                    #print(\"?\",pre)\n",
    "                    cur *= 2\n",
    "                arr[-1] += cur\n",
    "                #print(arr[-1],cur)\n",
    "            pre = c\n",
    "        #print(arr)\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = [0]\n",
    "        for v in s:\n",
    "            if v=='(':\n",
    "                stack.append(0)\n",
    "            else:\n",
    "                tmp = stack.pop()\n",
    "                stack[-1] += max(2*tmp,1)\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = [0]\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                stack.append(0)\n",
    "            else:\n",
    "                top = stack.pop()\n",
    "                if top == 0:\n",
    "                    stack[-1] += 1\n",
    "                else:\n",
    "                    stack[-1] += 2*top\n",
    "        return sum(stack)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # stack = [0]\n",
    "        # for i in s:\n",
    "        #     if i == \"(\":\n",
    "        #         stack.append(0)\n",
    "        #     else:\n",
    "        #         top = stack.pop()\n",
    "        #         if top == 0:\n",
    "        #             stack[-1] += 1\n",
    "        #         else:\n",
    "        #             stack[-1] += 2*top\n",
    "        # return sum(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = bal = 0\n",
    "        for i, c in enumerate(s):\n",
    "            bal += 1 if c == '(' else -1\n",
    "            if c == ')' and s[i - 1] == '(':\n",
    "                ans += 1 << bal\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        #Divide & Conquor\n",
    "        start = 0 \n",
    "        end = len(s)-1\n",
    "        score = self.dfsHepler(s,start,end)\n",
    "        return score\n",
    "\n",
    "    def dfsHepler(self,s,start,end):\n",
    "        \n",
    "        if start > end:\n",
    "            return 0  \n",
    "        \n",
    "        score= 0 \n",
    "        nleft = 0 \n",
    "        nright = 0 \n",
    "        nextStart = start \n",
    "\n",
    "        for i in range(start,end+1):\n",
    "            if s[i] == '(':\n",
    "                nleft += 1 \n",
    "            elif s[i] == ')':\n",
    "                nright += 1\n",
    "            if nleft != 0 and nright != 0 and nleft == nright:\n",
    "                if nleft == 1 and nright == 1:\n",
    "                    score += 1 \n",
    "                    nleft = 0\n",
    "                    nright = 0\n",
    "                    nextStart = i + 1\n",
    "                else:\n",
    "                    score += self.dfsHepler(s,nextStart+1,i-1)*2\n",
    "                    nleft = 0\n",
    "                    nright = 0\n",
    "                    nextStart = i + 1 \n",
    "        \n",
    "        return score\n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scoreOfParentheses(self, s: str) -> int:\r\n",
    "        s=s.replace('()','1')\r\n",
    "        cnt=0\r\n",
    "        res=0\r\n",
    "        for i in s:\r\n",
    "            if i=='(':\r\n",
    "                cnt+=1\r\n",
    "            elif i=='1':    \r\n",
    "                res+=1<<cnt\r\n",
    "            else:\r\n",
    "                cnt-=1\r\n",
    "                    \r\n",
    "\r\n",
    "        return res           \r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                stack.append(ch)\n",
    "            else:\n",
    "                current_score = 0\n",
    "                while stack and isinstance(stack[-1], int):\n",
    "                    current_score += stack.pop()\n",
    "                \n",
    "                stack.pop()\n",
    "\n",
    "                stack.append(1 if current_score == 0 else 2 * current_score)\n",
    "        \n",
    "        return sum(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scoreOfParentheses(self, s: str) -> int:\r\n",
    "        res,level=0,0\r\n",
    "        for i,c in enumerate(s):\r\n",
    "            if c=='(':\r\n",
    "                level+=1\r\n",
    "            else:\r\n",
    "                level-=1\r\n",
    "            if c==')' and s[i-1]=='(':\r\n",
    "                res+=1<<(level)\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = bal = 0\n",
    "        for i, c in enumerate(s):\n",
    "            bal += 1 if c == '(' else -1\n",
    "            if c == ')' and s[i - 1] == '(':\n",
    "                ans += 1 << bal\n",
    "                print(ans)\n",
    "                print(s[:i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack = [0] # 记录当前括号内的分数\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"(\":\n",
    "                stack.append(0)\n",
    "            else:\n",
    "                val = stack.pop()\n",
    "                stack[-1] += val * 2 if val > 0 else 1\n",
    "        return stack[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        stack=[0]\n",
    "        for s1 in s:\n",
    "            if s1=='(':\n",
    "                stack.append(0)\n",
    "            else:\n",
    "                v=stack.pop()\n",
    "                stack[-1]+=max(2*v,1)\n",
    "        return stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        # def f(x=0) -> int:\n",
    "        #     return max(2*x, 1)\n",
    "\n",
    "        # s = s.replace(')(', ')+(').replace('(', 'f(')\n",
    "        # return eval(s)\n",
    "\n",
    "        # 栈\n",
    "        # st = [0]\n",
    "        # for i in s:\n",
    "        #     if i == '(':\n",
    "        #         st.append(0)\n",
    "        #     else:\n",
    "        #         v = st.pop()\n",
    "        #         st[-1] += max(2*v, 1)\n",
    "        # return st[-1]\n",
    "\n",
    "        # 计算最终分数和\n",
    "        ans = bal = 0\n",
    "        for i, c in enumerate(s):\n",
    "            bal += 1 if c == '(' else -1\n",
    "            if c == ')' and s[i-1] == '(':\n",
    "                ans += 1 << bal\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        idx=[-1]*n\n",
    "        stk=[]\n",
    "        for i in range(n):\n",
    "            if stk and s[stk[-1]]==\"(\" and s[i]==\")\":\n",
    "                j=stk.pop()\n",
    "                idx[j]=i\n",
    "                idx[i]=j\n",
    "            else:\n",
    "                stk.append(i)\n",
    "        def dfs(i,j):\n",
    "            if i+1==j:\n",
    "                return 1\n",
    "            elif idx[j]==i:\n",
    "                return dfs(i+1,j-1)*2\n",
    "            else:\n",
    "                k=idx[i]\n",
    "                return dfs(i,k)+dfs(k+1,j)\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        left_num = 0\n",
    "        res = 0\n",
    "        right_num = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                left_num += 1\n",
    "            elif s[i] == ')':\n",
    "                if i + 1 < len(s) and s[i + 1] == ')':\n",
    "                    right_num += 1\n",
    "                else:\n",
    "                    res += 2 ** (left_num - 1)\n",
    "                    left_num -= right_num + 1\n",
    "                    right_num = 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    # class Stack:\r\n",
    "    #     def __init__(self):\r\n",
    "    #         self.lista = []  # 创建空栈\r\n",
    "\r\n",
    "    #     def isEmpty(self):\r\n",
    "    #         return len(self.lista) == 0\r\n",
    "\r\n",
    "    #     def push(self, item):\r\n",
    "    #         self.lista.append(item)\r\n",
    "\r\n",
    "    #     def pop(self):\r\n",
    "    #         return self.lista.pop()\r\n",
    "\r\n",
    "    #     def top(self):\r\n",
    "    #         return self.lista[-1]\r\n",
    "\r\n",
    "    # def check(self, s):\r\n",
    "    #     stack = self.Stack()\r\n",
    "    #     for i in range(len(s)):\r\n",
    "    #         if stack.isEmpty() or s[i] == \"(\":\r\n",
    "    #             stack.push(s[i])\r\n",
    "    #         else:\r\n",
    "    #             if stack.top() == \"(\":\r\n",
    "    #                 stack.pop()\r\n",
    "    #             else:\r\n",
    "    #                 stack.push(s[i])\r\n",
    "    #     return stack.isEmpty()\r\n",
    "\r\n",
    "    # def scoreOfParentheses(self, s: str) -> int:\r\n",
    "    #     if s == \"()\":\r\n",
    "    #         return 1\r\n",
    "    #     elif self.check(s[1 : len(s) - 1]):\r\n",
    "    #         return 2 * self.scoreOfParentheses(s[1 : len(s) - 1])\r\n",
    "\r\n",
    "    #     else:\r\n",
    "    #         for i in range(len(s)):\r\n",
    "    #             if self.check(s[0 : i + 1]):\r\n",
    "    #                 return self.scoreOfParentheses(\r\n",
    "    #                     s[0 : i + 1]\r\n",
    "    #                 ) + self.scoreOfParentheses(s[i + 1 :])\r\n",
    "\r\n",
    "    def scoreOfParentheses(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        if n == 2:\r\n",
    "            return 1\r\n",
    "        bal = 0\r\n",
    "        for i, c in enumerate(s):\r\n",
    "            bal += 1 if c == \"(\" else -1\r\n",
    "            if bal == 0:\r\n",
    "                if i == n - 1:\r\n",
    "                    return 2 * self.scoreOfParentheses(s[1:-1])\r\n",
    "                return self.scoreOfParentheses(s[: i + 1]) + self.scoreOfParentheses(\r\n",
    "                    s[i + 1 :]\r\n",
    "                )\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, s: str) -> int:\n",
    "        ans = bal = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if x == '(':\n",
    "                bal += 1\n",
    "            else:\n",
    "                bal -= 1\n",
    "                if s[i-1] == '(':\n",
    "                    ans += 1<< bal\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # stk = []\n",
    "        # stk.append(0)\n",
    "        # for c in s:\n",
    "        #     if c=='(':\n",
    "        #         stk.append(0)\n",
    "        #     else:\n",
    "        #         v = stk[-1]\n",
    "        #         stk.pop()\n",
    "        #         w = stk[-1]\n",
    "        #         stk.pop()\n",
    "        #         stk.append(w+max(2*v,+))\n",
    "        # return stk[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
